package com.kethink.clsssify;

import sun.reflect.generics.tree.Tree;

import java.util.Stack;

public class BinaryTree {

    private TreeNode root = null;

    public BinaryTree(){
        root = new TreeNode(1,"A");
    }


    /**
     * 构建一个二叉树
     *              A
     *         B         C
     *    D         E           F
     *
     */
    public void createBinaryTree(){
        TreeNode nodeB = new TreeNode(2,"B");
        TreeNode nodeC = new TreeNode(2,"C");
        TreeNode nodeD = new TreeNode(2,"D");
        TreeNode nodeE = new TreeNode(2,"E");
        TreeNode nodeF = new TreeNode(2,"F");
        root.leftChild = nodeB;
        root.rightChild = nodeC;
        nodeB.leftChild = nodeD;
        nodeB.rightChild = nodeE;
        nodeC.rightChild = nodeF;
    }

    public TreeNode createBinaryTree(int index ,String str){

        char[] array = str.toCharArray();
        TreeNode treeNode;
        if(index >= str.length()){
            treeNode = null;
            return treeNode;
        }
        char c = array[index];
        System.out.println("当前字符是："+c);
        if ("#".equals(c+"")){
            treeNode = null;
        }else {

            treeNode = new TreeNode(index,c+"");
            if(index == 0){
                root = treeNode;
            }
            treeNode.leftChild = createBinaryTree(++index,str);
            treeNode.rightChild = createBinaryTree(++index,str);
        }

        return treeNode;
    }

    /**
     * 获取当前二叉树的深度
     * @return
     */
    public  int getHeight(){
        return getHeight(root);
    }

    /**
     * 获取某个二叉树的深度
     * @param node
     * @return
     */
    public int getHeight(TreeNode node){

        if(node == null){
            return 0;
        }else {
            int left = getHeight(node.leftChild);
            int right = getHeight(node.rightChild);
            return (left>right ? left + 1 : right + 1);
        }
    }

    /**
     * 获取当前二叉树的结点个数
     * @return
     */
    public int getSize(){
        return getSize(root);
    }

    /**
     * 获取某个二叉树的结点个数
     * @param node
     * @return
     */
    private int getSize(TreeNode node) {

        if (node == null){
            return 0;
        }else {
            int leftSize = getSize(node.leftChild);
            int rightSize = getSize(node.rightChild);
            return 1 + leftSize + rightSize;
        }
    }


    /**
     * 二叉树的前序遍历
     * @param node
     */
    public void preOrder(TreeNode node){
        if(node == null){
            return;
        }else {
            System.out.print(node.getData() + "  ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public void midOrder(TreeNode node){
        if(node == null){
            return;
        }else {
            midOrder(node.leftChild);
            System.out.print(node.getData() + "  ");
            midOrder(node.rightChild);
        }
    }


    /**
     * 后序遍历
     * @param node
     */
    public void postOrder(TreeNode node){
        if (node == null){
            return;
        }else {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.getData() + "  ");
        }

    }

    /**
     * 非迭代方法的前序遍历
     * @param node
     */
    public void nonRecPreOrder(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(node);

        while (!stack.isEmpty()){
            TreeNode n = stack.pop();
            System.out.print(n.getData()+"  ");
            //先进后出
            if(n.rightChild != null){
                stack.push(n.rightChild);
            }
            //后进先出
            if(n.leftChild != null){
                stack.push(n.leftChild);
            }

        }
    }


    /**
     * 非迭代方法的中序遍历
     * @param node
     */
    public void nonRecMidOrder(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if(node.leftChild != null){
            stack.push(node.leftChild);
        }else {
            stack.push(node);
        }
        TreeNode currTreeNode = node;
        while (!stack.isEmpty()){

            TreeNode n = stack.pop();

            //先进后出
            if(n.rightChild != null){
                stack.push(n.rightChild);
            }

            System.out.print(n.getData()+"  ");

            while (currTreeNode.leftChild != null){
                if(currTreeNode.rightChild != null){
                    stack.push(currTreeNode.rightChild);
                }
                currTreeNode = node.leftChild;
            }
            if(currTreeNode.leftChild == null){
                System.out.print(currTreeNode.getData() + "  ");
            }

        }
    }

    /**
     * 非迭代方法的后序遍历
     * @param node
     */
    public void nonRecPostOrder(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(node);

        while (!stack.isEmpty()){
            TreeNode n = stack.pop();

            //先进后出
            if(n.rightChild != null){
                stack.push(n.rightChild);
            }
            //后进先出
            if(n.leftChild != null){
                stack.push(n.leftChild);
            }
            System.out.print(n.getData()+"  ");

        }
    }



    public static void main(String[] args){
        BinaryTree tree = new BinaryTree();

        String ss = "ABD##E##C#F##";

        tree.createBinaryTree(0,ss);

        System.out.println("Size = "+ tree.getSize());
        System.out.println("Height = "+ tree.getHeight());

        tree.preOrder(tree.root);

        System.out.println();
        tree.midOrder(tree.root);
        System.out.println();
        tree.postOrder(tree.root);

//        System.out.println();
//        tree.nonRecPreOrder(tree.root);
//        System.out.println();
//        tree.nonRecMidOrder(tree.root);
//        System.out.println();
//        tree.nonRecPostOrder(tree.root);
    }



    public class TreeNode{
        private int index;
        private String data;
        private TreeNode leftChild;
        private TreeNode rightChild;

        public TreeNode(){

        }

        public TreeNode(int index, String data){
            this.index = index;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }



    }



}
